package greed;

public class jump {
    // Integer rs = Integer.MAX_VALUE;
    //反着来会更好
    public int jump(int[] nums) {
        int rs =0;
        int pos=nums.length-1;
        while (pos>0) {
            //尽可能的往前找
            int i=1,offset=0;
            //前面可能还有机会，不能因为一个不行就放弃了
            while (pos-i>=0) {
                if (nums[pos-i]>=i) {
                    offset=i;
                }
                i++;
            }
            pos-=offset;
            rs++;
        }
        //想着用回溯
        // backtrack(nums, 0,0);
        return rs;
    }
    // public void backtrack(int[]nums,int pos,int count){
    //     if (pos==nums.length-1) {
    //         rs = Math.min(rs, count);
    //         return;
    //     }
    //     int value = nums[pos];
    //     for(int i=1;i<=value;i++){
    //         int index = i+pos;
    //         if (index>=nums.length) {
    //             break;
    //         }
    //         backtrack(nums, index, count+1);
    //     }

    // }
    public static void main(String[] args) {
        jump obj = new jump();
        // int[] nums= new int[]{2,3,1,1,4};
        // int[] nums= new int[]{2,2,0,1,4};
        int[] nums= new int[]{5,6,4,4,6,9,4,4,7,4,4,8,2,6,8,1,5,9,6,5,2,7,9,7,9,6,9,4,1,6,8,8,4,4,2,0,3,8,5};
        System.out.println(obj.jump(nums));
    }
}
